Modern cryptographic methods require massive numbers of basic arithmetic operations such as addition, subtraction, multiplication, division, remainder, shift, and logical ‘and’, ‘or’, and ‘xor’. Many of these methods require computation of powers Ak (respectively multiples k*A) for a value k that is selected at random from a large set of possible values.
Heretofore a variety of methods have been proposed and implemented for computing powers Ak (respectively multiples k*A) for a specified value of k (H. Cohen, A Course in Computational Number Theory, GTM 138, Springer-Verlag, 1993 (Section 1.2)), (D. Gordon, A survey of fast exponentiation methods, Journal of Algorithms 27 (1998), 129–146), (D. Knuth, The Art of Computer Programming, Volume 2, Seminumerical Algorithms, 3rd ed., Addison-Wesley, 1998 (Section 6.4.3)), (A. J. Menezes, et al., Handbook of Applied Cryptography, CRC Press, 1997 (Section 14.6)).
One type of rapid computational method which has been used is to write k as a sum of powers of two to reduce the computation to multiplications and squarings (respectively additions and doublings).
A second type of rapid computational method which has been used is to write k as a sum of plus and minus powers of two to reduce the computation to multiplications, inversions, and squarings (respectively additions, subtractions, and doublings).
A third type of rapid computational method which has been used is to write k as a sum of small multiples of powers of two to reduce the computation to multiplications, small powers, and squarings (respectively additions, subtractions, small multiples, and doublings).
A fourth type of rapid computation method which has been used is to write k as a sum of powers of a special multiplier t, where t has the property that raising to the t power (respectively multiplying by t) takes very little time compared to multiplication (respectively addition or subtraction). A particular instance of this method is writing k as a sum of powers of the p-power Frobenius map on the group of points E(GF(pm)) on an elliptic curve E defined over the finite field GF(p).
A fifth type of rapid computation method which has been used (called the factor method (Knuth, supra, Section 4.6.3, page 463 and exercise 3)) is to write a given integer k as a product of factors which are themselves written using one of the previously described methods.
All of these methods allow reasonably rapid computation of powers Ak (or multiples k*A) for all or most values of k, but many users would find it desirable to have a method which allows even more rapid computation of powers Ak (or multiples k*A) with k taken from a sufficiently large set of allowable values.